#ifndef _hash_
#define _hash_

#include<iostream>
#include<string>

#define size 2099
#define multiplier 31

class node
{
private:
    std::string word ;
    int number=0;
    node* next=NULL;
public:
    node() {++number;};
    node(std::string s) {word=s;++number;};
    std::string getword() const {return word;};
    int getnumber() const {return number;};
    node* getnext() const {return next;};
    node** getadd() {return &next;};
    void setword(std::string w) {word=w;};
    void setnext(node* n) {next=n;};
    void count() {++number;};
};

class hashtable
{
private:
    node* table[size]={NULL};
    void hash(std::string s);
    void insert(node** slotpointer, std::string s);
public:
    hashtable(){};
    ~hashtable(){
        for(int i=0;i<size;++i){
            node* slot=table[i];
            while(slot!=NULL){
                node* tmp=slot->getnext();
                delete slot;
                slot=tmp;
                                 
            }
        }
    };
    void input();
    void output() const;
    void top20() const;
};

void hashtable::hash(std::string s)
{
    if(s.size()==0) return;
    long result=0;
    for(std::string::iterator it=s.begin();it!=s.end();it++){
        char c=*it;
        if(c>='A' && c<='Z'){
            result=result*multiplier+int(c)-64;
            *it=c+'a'-'A';
        }
        else if(c>='a' && c<='z') result=result*multiplier+int(c)-96;
        else if(c==39){};
        else{
            if(it>s.begin()){
                std::string sl(s.begin(),it);
                hashtable::hash(s1);
            }
            if(it<s.end()-1){
                std::string s2(it+1,s.end());
                hashtable::hash(s2)
            }
            return;
        }
    }
    hashtable::insert(table+result%size,s);
};

void hashtable::insert(node** slotpointer,std::string s){
    if(*slotpointer NULL){
        node* tmp=new node(s);
        (*slotpointer)=tmp;
        return;
    }
    else if((*slotpointer)->getword()==s){
        (*slotpointer)->count();
        return;
    }
    else{
        insert((*slotpointer)->getadd(),s);
        return;
    }
};

void hashtable::input(){
    std::string str;
        while(std::cin >> str){
            hashtable::hash(str);
        }
        return;
};

void hashtable::output() const{
    for(int i=0;i<size;++i){
        node*slot=table[i];
        while(slot!=NULL){
            std::cout << slot->getword();
            std::cout << " " << slot->getnumber() << "\n";
            slot=slot->getnext();
        }
    }
    return;
};

